Typically, due to the connectionless nature of Internet Protocol (IP) networks, IP-routers do not maintain per-flow states. The gathering of flow-level statistics, however, is required for performing various network management functions such as network traffic planning and management, monitoring for service level compliance, detecting potential denial-of-service attacks, and the like. It is generally difficult to determine such statistics, which include the number of packets sent between pairs of hosts over a certain link during a certain time period, traffic pattern changes over time, and the like. In other words, accurate flow rate estimation is necessary for network planning, traffic management, service level assurance, network security, and like management functions.
In a “naïve counting” approach, flow counters must be maintained for all flows in the network, and each flow counter must be accessed for each arrival. Such “naïve counting” requires significant memory usage, rendering naïve counting prohibitively expensive. In a “heavy-hitters” approach, sampling is performed for selecting heavy-hitter flows having flow rates above a threshold, and all packets belonging to a heavy-hitter flow are counted. However, deriving the number of samples required to achieve a specified estimation accuracy is prohibitively difficult. In a “smart-sampling” approach, random packets from the arriving packets are sampled, and packets are assigned weights based on packet length for estimating flow bit-rates. However, the sampling accuracy is bounded by available memory, and the sampling result may be inaccurate.